package com.example.demo.arithmetic.algorithm.greedy.bag;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 2. 背包问题（0/1 Knapsack Problem）
 * 问题描述：给定一组物品，每个物品有重量和价值，
 * 在给定的最大重量限制下，选择物品使得总价值最大。
 * <p>
 * 解决方法：
 * 对于0/1背包问题，贪心算法并不能保证得到最优解。
 * 然而，对于分数背包问题（Fractional Knapsack Problem），
 * 可以使用贪心算法。选择单位价值最高的物品，直到达到重量限制。
 */
//、分数背包问题
// 1.n个物品都是液体 ，有重量 和 价值
// 2.现在你要取走10L液体
// 3.每次可以不拿 全拿 或者拿一部分 求能拿走的最高价值
//    拿单价最高的么
//  编号  单价  重量（升） 价值
//    0     6    4          24      水
//    1     20   8          160     牛奶
//    2   2000   2          4000    五粮液
//    3     16   6          108     可乐
//    4   4000   1          4000    茅台
public class BagProblem {

    public static class Item {
        public int price;
        public int weight;
        public int sum;
        public int index;

        public Item(int index, int weight, int sum) {
            this.price = sum / weight;
            this.weight = weight;
            this.sum = sum;
            this.index = index;
        }

        @Override
        public String toString() {
            return "Item{" +
                    "price=" + price +
                    ", weight=" + weight +
                    ", sum=" + sum +
                    '}';
        }
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(0, 4, 24),
                new Item(1, 8, 160),
                new Item(2, 2, 4000),
                new Item(3, 6, 108),
                new Item(4, 1, 4000)
        };

        System.out.println(new BagProblem().maxValue(items, 10));
    }

    public int maxValue(Item[] items, int targetWight) {
        // 优先选单价最贵的 -item.price就是降序了 太骚了实在是！！
        Arrays.sort(items, Comparator.comparing(item -> -item.price));
        //        System.out.println(Arrays.toString(items));
        int count = 0;
        for (Item item : items) {
            if (item.weight > targetWight) { // 只拿一部分
                count += targetWight * item.price;
                break;
            } else {
                // 你要的全拿走
                targetWight -= item.weight;
                count += item.sum;
            }
        }
        return count;
    }
}
